The provision of negotiated Quality-of-Service (QoS) guarantees such as data transfer rate and data transfer delay to traffic generated by applications of widely different characteristics is a primary objective in packet networks. In such networks, when network resources such as communication links are shared among a plurality of network connections, sophisticated packet scheduling disciplines are necessary to satisfy the QoS requirements of delay-sensitive network connections. A server in a communication system providing such QoS guarantees typically employs multiple queues, in which each queue is associated with a corresponding network connection, and uses a scheduling algorithm to control the order in which the individual queues are served.
One such sophisticated scheduling algorithm is the Generalized Processor Sharing (GPS) scheduling policy. GPS is an idealized scheme which guarantees a negotiated minimum data transfer rate to each network connection, regardless of the behavior of other connections. GPS also guarantees a negotiated maximum end-to-end data transfer delay to each connection, and ensures that all connections are served in a fair manner. During any time interval, a GPS server serves all backlogged queues, i.e., queues which have packets waiting to be transmitted, simultaneously, each with an instantaneous service rate that is a function of the negotiated data transfer rate and delay associated with the respective connection. It can be appreciated that, because all connections have to be serviced simultaneously, the GPS algorithm cannot be implemented in a real packet network, and, therefore. is considered to be an ideal scheduling discipline.
A class of scheduling disciplines, called GPS-related packet-scheduling disciplines, which approximate the GPS scheduling policy to a certain degree, may be implemented in a real packet network. These algorithms are all based on maintaining a global function, referred to as virtual time or as system potential, which is a measure of the amount of service that has been provided by a server. A server uses this global function to compute a finishing virtual time, also referred to as timestamp, for each packet in the associated system; in which the timestamp is indicative of when the service of the corresponding packet should be completed. The server serves the packets based on the values of their respective timestamps, starting with the smallest value. The GPS-related packet-scheduling disciplines differ from one another in the specific function used as virtual time. Similarly to GPS, all the GPS-related packet-scheduling disciplines provide a negotiated minimum data transfer rate to each network connection. The specific virtual-time function that is used by each such discipline determines the implementation complexity of the algorithm, the value of the maximum data transfer delay that the algorithm can provide to a connection, and whether or not the algorithm serves all connections in a fair manner. An algorithm that is of minimum complexity, provides a small value of the maximum data transfer delay to each connection, and serves all connections fairly, is highly desirable.
One example of a GPS-related packet-scheduling discipline is the so called Packet-by-packet GPS (P-GPS) algorithm. P-GPS guarantees maximum data transfer delays very close to those of GPS, and serves the connections almost as fairly as GPS. P-GPS uses a system-potential function that is directly derived from a background simulation of GPS. However, P-GPS is not practical in high-speed packet networks, since the task of simulating GPS is very complex. Another example of a GPS-related packet-scheduling discipline is a so called Self-Clocked Fair Queueing (SCFQ) algorithm. SCFQ has minimum implementation complexity, which makes it practical for implementation in high-speed packet networks. It also serves the connections almost as fairly as GPS. However, SCFQ guarantees maximum data transfer delays that are much larger than those that are guaranteed by GPS and P-GPS. Another example of a GPS-related packet-scheduling discipline is a so called Virtual Clock algorithm. The Virtual Clock algorithm has a minimum implementation complexity; and it also guarantees maximum data transfer delays very close to those of GPS and P-GPS. However, it does not always serve all connections in a fair manner. Still another example of a GPS-related packet-scheduling discipline is a Starting-Potential Fair Queueing (SPFQ) algorithm. The SPFQ algorithm guarantees maximum data transfer delays very close to those of GPS and P-GPS, and serves the connections almost as fairly as GPS and P-GPS. However, the implementation complexity of the SPFQ algorithm is considerably higher than either of the SCFQ and Virtual Clock algorithms.
Other GPS-related packet-scheduling disciplines, in addition to the four examples listed above, are known in the relevant art. However, none of these GPS-related packet-scheduling disciplines has all of the qualities that are desirable in a packet scheduler, i.e., a packet scheduler which has minimum complexity, provides a small value of the maximum data transfer delay to each connection, and serves all connections fairly.